package examination_practice01;

import ADD_project.MaximumPathSum;

import java.util.Scanner;

public class TriangleMaxSum {
    public static void main(String[] args){
        System.out.println("请输入三角形的高");
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println("请输入三角型数据");
        int[][] triangle=new int[n][n];

        //输入数学三角形
        for (int i=0;i<n;i++){
            for (int j=0;j<=i;j++){
                triangle[i][j]=sc.nextInt();
            }
        }

        int[][] dp=new int[n][n];
        //初始化最后一行
        for (int j=0;j<n;j++){
            dp[n-1][j]=triangle[n-1][j];
        }

        //自底向上求最大路径和
        for (int i=n-2;i>=0;i--){
            for (int j=0;j<=i;j++){
                dp[i][j]= Math.max(dp[i+1][j],dp[i+1][j+1]+triangle[i][j]);

            }
        }
        //取到路径的最大值
        int maxPathSum=dp[0][0];
        System.out.println("路径最大值为："+maxPathSum);
    }
}
